#include <iostream>
using std::cout;
using std::endl;

// 斐波那契数列，以兔子繁殖为例子而引入，故又称为“兔子数列”
// 1 1 2 3 5 8 13 21 34...这个数列从第3项开始，每一项都等于前两项之和
// 类似问题：排列组合(上台阶)、黄金分割、矩形面积...
// ------------------------------------------------------------
// 求解算法：递归/递归记忆、循环、数组、动态规划等
// 递归 求第N个数，时间复杂度为O(n^2)，不是一个好算法
int Fibnacci(int n) {
  static int count = 0;
  count++;
  cout << __FUNCTION__ << ' ' << count << " times" << endl;
  if (n == 1) return 1;
  if (n == 2) return 1;
  return Fibnacci(n - 1) + Fibnacci(n - 2);
}

void TestFibnacci() {
  int n = 8;
  cout << Fibnacci(n) << " Fibnacci" << endl;
}

// 全排列问题
// 求1 2 3 4这N个数可能出现的所有排列个数
int PermutationsCount(int n) {
  if (n == 1) return 1;
  return PermutationsCount(n - 1) * n;
}

// 打印全排列。时间复杂度介于 O(n!)到 O(n∗n!)之间
// f(1,2,...n) = {f(n-1),1} + {f(n-1),2} +...+{f(n-1),n}
// k表示要处理的子数组的元素个数
void PermutationsPrint(int arr[], int n, int k) {
  if (k == 1) {
    for (int i = 0; i < n; ++i) {
      cout << arr[i] << ' ';
    }
    cout << endl;
  }

  // 数组{0,1,2,3}，k==4
  for (int i = 0; i < k; ++i) {
    std::swap(arr[i], arr[k - 1]);
    PermutationsPrint(arr, n, k - 1);
    std::swap(arr[i], arr[k - 1]);
  }
  // i==0时：{3,1,2,0}，处理前三个，还原{0,1,2,3}
  // i==1时：{0,3,2,1}，处理前三个，还原{0,1,2,3}
  // i==2时：idx2交换到最后一位，处理前三个，再交换回来
  // i==3时：idx3交换到最后一位，处理前三个，再交换回来
}

void TestPermutations() {
  int arr[] = {0, 1, 2, 3};
  int n = sizeof(arr) / sizeof(int);
  cout << "PermutationsCount:" << PermutationsCount(n) << endl;
  PermutationsPrint(arr, n, n);
}

int main() {
  TestFibnacci();
  cout << endl;
  TestPermutations();
}